package sort;

import java.util.Stack;

/**
 * 快速排序
 */

/**
 * 时间复杂度：最好：O(N*logN) 最坏：O(N*N)
 * 空间复杂度：最好：O(logN) 最坏：O(N)
 * 稳定性：不稳定
 */
public class QuickSort implements ISort{

    private void insertSort(int[] array,int left,int right) {
        for(int i = left; i <= right; i++) {
            for(int j = i - 1; j >= 0; j--) {
                if(array[j] > array[j+1]) {
                    Swap.swap(array,j,j+1);
                }
            }
        }
    }
    private void quick(int[] array,int left,int right) {
        if(left >= right) {
            return;
        }
        //优化一：当数组中元素小于某个值，直接使用直接插入排序
        if(right - left + 1 < 15) {
            insertSort(array,left,right);
            return;
        }
        //优化二：三数取中法
        int mid = middle(array,left,right);
        Swap.swap(array,mid,left);

        int partition = partitionHole(array,left,right);

        quick(array,left,partition-1);
        quick(array,partition+1,right);
    }

    private int middle(int[] array, int left, int right) {
        int mid = (right + left) / 2;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]){
                return right;
            }else {
                return mid;
            }
        }else{
            if(array[mid] > array[left]) {
                return left;
            }else if(array[mid] < array[right]){
                return right;
            }else {
                return mid;
            }
        }
    }

    //挖坑法
    private int partitionHole(int[] array,int left,int right) {
        int tmp = array[left];
        while(left < right) {
            //先从后面找一个比tmp小的值
            while(left < right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while(left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

    @Override
    public void sort(int[] array) {
        quick(array,0,array.length-1);
    }

    /**
     * 快排非递归实现
     * @param array
     */
    public void sortNor(int[] array) {
        int left = 0;
        int right = array.length - 1;
        int partition = partitionHole(array,left,right);
        Stack<Integer> stack = new Stack<>();
        if(partition - 1 > left) {
            stack.push(left);
            stack.push(partition - 1);
        }
        if(partition + 1 < right) {
            stack.push(partition + 1);
            stack.push(right);
        }
        while(!stack.isEmpty()) {
            left = stack.pop();
            right = stack.pop();
            partition = partitionHole(array,left,right);
            if(partition - 1 > left) {
                stack.push(left);
                stack.push(partition - 1);
            }
            if(partition + 1 < right) {
                stack.push(partition + 1);
                stack.push(right);
            }
        }
    }
}
